<html>
<head>
    <meta charset="UTF-8">
    <meta name="copyright" content="stewart allen [sa@grid.space]">
    <meta name="description" content="gyroid infill code playground">
    <meta name="keywords" content="gyroid,infill" />
    <meta name="author" content="Stewart Allen">
    <meta name="robots" content="noindex, nofollow">
    <meta property="og:description" content="algorithm testing sandbox">
    <meta property="og:title" content="gyroid infill playground">
    <meta property="og:type" content="website">
    <meta property="og:url" content="https://grid.space/kiri/gyroid-test.html">
    <title>gyroid testing</title>
    <style>
        body {
            display: flex;
            flex-direction: row;
            justify-content: center;
        }
        #test {
            display: flex;
            flex-direction: column;
            justify-content: center;
            align-items: stretch;
        }
        #gyroid > div {
            display: flex;
            flex-direction: row;
        }
        #gyroid > div > div {
            min-width: 3px;
            min-height: 3px;
        }
        #stats {
            text-align: center;
        }
        #stats > input {
            pointer-events: none;
            outline: none;
            width: 5em;
        }
        svg {
            border: 1px solid #888;
        }
    </style>
    <script>
        let PI2 = Math.PI * 2;
        let rez = 200;
        let inc = PI2 / rez;
        let zcache = {};

        function $(id) {
            return document.getElementById(id);
        }

        function init() {
            $('zval').max = rez;
            for (let z=0; z<PI2; z += inc) {
                generate(z);
            }
            render(0);
        }

        function update() {
            let z = $('zval').value;
            render((z / rez) * PI2);
        }

        function generate(z) {
            let zkey = z.toFixed(8);
            let cached = zcache[zkey];

            if (cached) {
                return cached;
            }

            let edge = [];
            let vals = [];
            let points = 0;
            let points_lr = 0;
            let points_td = 0;
            for (let x=0; x<PI2; x += inc) {
                let vrow = []; // raw values row
                let erow = []; // edge values row
                edge.push(erow);
                vals.push(vrow);
                for (let y=0; y<PI2; y += inc) {
                    erow.push(0);
                    vrow.push(
                        Math.sin(x) * Math.cos(y) +
                        Math.sin(y) * Math.cos(z) +
                        Math.sin(z) * Math.cos(x)
                    );
                }
            }

            // left-right threshold search (red)
            vals.forEach((vrow, y) => {
                let erow = edge[y];
                let v0 = vrow[vrow.length - 1];
                vrow.forEach((v1, x) => {
                    if ((v0 <= 0 && v1 >= 0) || (v0 >= 0 && v1 <= 0)) {
                        erow[x] = 1;
                        points++;
                        points_lr++;
                    }
                    v0 = v1;
                })
            });

            // top-down threshold search (green)
            for (let x=0; x<rez; x++) {
                let v0 = vals[vals.length-1][x];
                for (let y=0; y<rez; y++) {
                    let v1 = vals[y][x];
                    if ((v0 <= 0 && v1 >= 0) || (v0 >= 0 && v1 <= 0)) {
                        if (edge[y][x]) {
                            edge[y][x] = 3;
                        } else {
                            edge[y][x] = 2;
                            points++
                        }
                        points_td++;
                    }
                    v0 = v1;
                }
            }

            // deterime prevailing direction for chaining
            let dir = points_td > points_lr ? 'lr' : 'td';

            // create sparse representation
            let sparse = [];
            let center = rez / 2;
            edge.forEach((row,y) => {
                row.forEach((val,x) => {
                    if (val) {
                        let dx = Math.abs(x - center);
                        let dy = Math.abs(y - center);
                        sparse.push({x, y, val, dist: Math.max(dx,dy)});
                    }
                });
            });
            sparse.sort((a,b) => {
                return b.dist - a.dist;
            });

            // preserve sparse points for rendering
            let raw = sparse.slice();

            // join sparse points array by closest distance
            let polys = [];
            let chain;
            let added;
            let cleared = 0;
            let maxdist = rez * 0.05;

            do {
                chain = null;
                for (let i=0; i<sparse.length; i++) {
                    if (sparse[i]) {
                        chain = [ sparse[i] ];
                        polys.push(chain);
                        sparse[i] = null;
                        cleared++;
                        break;
                    }
                }
                do {
                    added = false;
                    let target = chain[chain.length - 1];
                    let cl_elm = null;
                    let cl_idx = null;
                    let cl_dst = Infinity;
                    for (let i=0; i<sparse.length; i++) {
                        let test_el = sparse[i];
                        if (test_el) {
                            let dst = dist(target, test_el, dir);
                            if (cl_idx === null || dst < cl_dst) {
                                cl_idx = i;
                                cl_elm = test_el;
                                cl_dst = dst;
                            }
                        }
                    }
                    if (cl_elm) {
                        if (cl_dst > maxdist) {
                            break;
                        }
                        sparse[cl_idx] = null;
                        cleared++;
                        chain.push(cl_elm);
                        added = true;
                    }
                } while (added);
            } while (cleared < sparse.length);

            // simplify poly
            polys = polys.map(poly => filter(poly));

            return zcache[zkey] = { raw, points, dir, polys };
        }

        function filter(poly) {
            if (poly.length <= 2) {
                return poly;
            }
            let nuchain = [ poly[0] ];
            let e1 = poly[1];
            let e2 = null;
            let last = poly.length - 2;
            for (let i=1; i<poly.length; i++) {
                let el = poly[i];
                if (e1.x === el.x || e1.y === el.y) {
                    e2 = el;
                    if (i < last) {
                        continue;
                    }
                }
                if (e2) {
                    nuchain.push({x:(e1.x + e2.x)/2, y:(e1.y + e2.y)/2});
                    e2 = null;
                } else {
                    nuchain.push(e1);
                    if (i === last) {
                        nuchain.push(el);
                    }
                }
                e1 = el;
            }
            nuchain.push(poly[poly.length-1]);
            return nuchain;
        }

        function dist(a, b, dir) {
            let dx = a.x - b.x;
            let dy = a.y - b.y;
            // bias distance by prevailing direction of discovery to join stragglers
            if (dir === 'lr') dx = dx / 2;
            if (dir === 'td') dy = dy / 2;
            return Math.sqrt(dx * dx + dy * dy);
        }

        function render(z) {
            let size = 600;
            let wh = size / rez;
            let html = [`<svg width=${size} height=${size}>`];
            let { raw, points, dir, polys } = generate(z);

            $('points').value = points;
            $('direction').value = dir;
            $('polys').value = polys.length;

            // raw threshold points
            html.push('<g>');
            raw.forEach(point => {
                let x = point.x;
                let y = point.y;
                let color = ['black','#f00a','#0f0a','#00fa'][point.val];
                html.push(`<rect dist="${point.dist}" x="${x*wh}" y="${y*wh}" width="${wh}" height="${wh}" style="fill:${color};stroke-width:0"/>`);
            })
            // polys.forEach(poly => {
            //     poly.forEach(point => {
            //         let x = point.x;
            //         let y = point.y;
            //         let color = ['black','#f00a','#0f0a','#00fa'][point.val];
            //         html.push(`<rect dist="${point.dist}" x="${x*wh}" y="${y*wh}" width="${wh}" height="${wh}" style="fill:${color};stroke-width:0"/>`);
            //     });
            // });
            html.push('</g>');

            // points joined into poly lines
            html.push('<g>');
            polys.forEach(poly => {
                let points = poly
                    .map(point => [point.x * wh + wh / 2, point.y * wh + wh / 2]
                    .join(',')).join(' ');
                let x = poly[0].x - 1;
                let y = poly[0].y - 1;
                html.push(`<rect x="${x*wh}" y="${y*wh}" width="${wh*3}" height="${wh*3}" style="fill:#f0f5;stroke-width:0"/>`);
                html.push(`<polyline points="${points}"/ fill="none" stroke="black" />`);
            });
            html.push('</g>');

            html.push('</svg>');

            $('gyroid').innerHTML = html.join('');
        }
    </script>
</head>
<body onload="init()">
    <div id="test">
        <div id="gyroid"></div>
        <input id="zval" type="range" min="0" max="200" value="0" oninput="update()"/>
        <div id="stats">
            <input id="points"></input>
            <input id="direction"></input>
            <input id="polys"></input>
        </div>
    </div>
</body>
</html>
